De-duplication may be referred to as “dedupe”. A dedupe data set may include, among other things, an index, a repository of sub-blocks, and re-creation information. The index may be configured to facilitate locating a stored sub-block. The re-creation information may be configured to facilitate assembling related sub-blocks into larger items (e.g., files). The repository of sub-blocks may be configured to facilitate accessing stored sub-blocks. A dedupe system creates and/or manages the data set to facilitate determining whether a sub-block under consideration is a duplicate sub-block or a unique sub-block and to facilitate reducing either the amount of duplicate data stored or the amount of duplicate data transmitted. The dedupe data set is stored on physical media on physical devices.
Different physical devices present different challenges and opportunities when supporting dedupe. For example, while a tape provides the opportunity to store extremely large amounts of data and the opportunity to perform efficient sequential input/output (i/o), tape may be challenged by seek times and thus challenged for random i/o. While a solid state device (SSD) built from, for example, flash memory, may provide the opportunity to perform efficient random input, an SSD may face challenges associated with the inability to perform random writes, page granularity for i/o, the inability to perform in-place updates, wear associated with frequently accessed areas, page writes being sequential only, and finite limits on erase/write cycles.
Thus attempts have been made to produce device specific techniques (e.g., tape-specific, SSD-specific) for supporting de-dupe. Generally these techniques have approached the issue “after the fact” (e.g., once data has already been de-duplicated) or inline (e.g., while the data is being compared to an existing data set). Generally these techniques have also approached the issue by addressing the well-known “index in RAM” issue associated with dedupe. While interesting and valuable, these approaches have been limited by when they are performed and their underlying assumptions about devices and dedupe.
For example, one conventional technique for using flash memory to support dedupe first identifies that flash memory tends to be faster than disk but slower than RAM, and that flash memory tends to be cheaper than RAM but more expensive than disk. This conventional technique also identifies that a dedupe index may not fit completely in RAM in a dedupe apparatus. Therefore, the conventional technique attempts to produce a flash “bridge” between RAM and disk that uses flash to replace disk and to support RAM while balancing cost versus speed. The bridge is used to store key-value pairs for the index in flash. The bridge migrates infrequently accessed key-value pairs to disk. The bridge attempts to reduce the RAM footprint of the index as much as possible by moving traditional index items (e.g., chunk location, chunk metadata) out of RAM and into flash. The bridge also attempts to reduce the RAM footprint of the index by not indexing every sub-block, but rather indexing only one sub-block per flash page. The bridge then uses pointers to pages of pointers to sub-blocks. Dedupe applications that use this conventional bridge may rely on hash collisions being resolvable in a small number of flash reads. While interesting and useful, this type of conventional technique appears to be focused on handling theoretical data sets rather than actual data sets about which actual data may be available.
One physical medium and device on which a dedupe data set may be stored is random access memory (RAM). RAM provides relatively fast random access as compared to other random access devices (e.g., disk). RAM is generally readily accessible to a processor executing dedupe processes. RAM is also relatively fast compared to other media. When sub-blocks are stored in RAM, the sub-blocks can be acquired using random accesses that may involve a bus access but no external i/o. Similarly, when information for re-creating a larger item (e.g., file) is stored in RAM, the information can be quickly accessed. Additionally, when the index is stored in RAM, index locations can be accessed using efficient random accesses.
Unfortunately, RAM is currently a finite resource and is also a relatively expensive resource as compared to other media (e.g., SSD, disk). Thus a device performing a de-duplication process likely has access to a finite amount of RAM. Since RAM is finite, neither all the sub-blocks for a dedupe data set, nor the re-creation information, nor the index can be stored completely in RAM. Therefore, at least some sub-blocks, re-creation information, and/or index portions are stored on some media and some device other than RAM. Conventionally, there may have been insufficient attention paid to how sub-blocks, re-creation information, and/or index portions should be arranged on these other storage media and devices. When attention was directed at how dedupe data, re-creation information, and/or index portions should be stored on other media and devices, the attention was typically applied at the generic, theoretical level, rather than at the actual observed data set level.
Disk is one additional storage medium and device used in dedupe. A disk generally includes a spinnable platter(s) with a movable read/write head(s). Disks, like RAM, are generally considered to be random access devices. While both RAM and disk provide random access, disk accesses generally take longer than RAM accesses because the platter(s) needs to be spun to a certain sector and the read/write head(s) need to be positioned over a certain track. Since the spinning and repositioning can be performed within a short enough period of time, the disk is considered to be random access. Thus, sub-blocks, re-creation information, and/or index portions may be available on disk through random accesses, although these random accesses are slower than random accesses to RAM. The disk may also be slower because the disk may not be as directly connected to a processor as RAM. For example, a disk may be connected through a disk controller that provides access to an external device.
Flash memory organized in an SSD is another storage medium used in dedupe. Flash memories tend to be organized using blocks of pages. In some flash-based SSDs, a page may be, for example, from 512 bytes to 16 k bytes and a block may include 8, 16, 32, 64, 128 or other numbers of pages. Flash memories support page reads and page writes rather than reads and writes of individual cells. Pages are written sequentially in a block. Flash memory supports a block erase. A block in a flash memory may have a finite lifetime measured in block erase cycles. For example, a block may only be able to be erased 10,000 times before its performance begins to degrade.
Flash memory supports random page reads but only sequential page writes. A random read from a flash memory has the same speed as a sequential read because there is no head movement required. Therefore, flash memory supports fast random reads but does not support random writes at all. Additionally, flash memory does not support actual in-place updates. Instead, to perform a pseudo-in-place update, a page write would have to be preceded by a block erase. Even then, a number of pages might have to be written sequentially. Conventional SSD supported dedupe may have configured an SSD as, for example, a circular append log. Page sized quantities of key-value pairs are buffered until an entire page is ready to write to the SSD. Conventional SSD supported dedupe may have employed buffering schemes and lookup schemes to avoid random writes to the SSD, to avoid writing less than a full page to SSD, and to avoid having cache misses that could lead to disk i/o. Once again, however, these conventional techniques appear to address theoretical data sets and theoretical devices “after the fact” of dedupe.
FIG. 1 illustrates the logical components 100 and the physical devices 110 described above. A dedupe data set may include an index 102, re-creation information 104, and a sub-block repository 106. These logical components 100 may be arranged in a variety of data structures. For example, an index 102 may be arranged as a linear index, as a binary tree, as an n-ary tree, and in other ways. The data structures are stored on physical devices 110. The physical devices 110 can include, but are not limited to, RAM 112, disk 114, and SSD 116. In different embodiments, the data structures are stored on combinations of the physical devices 110.
FIG. 2 illustrates a flash memory based SSD 200. Pages are organized into blocks. SSD 200 is illustrated with blocks 202, 212, and 222. Block 202 includes pages 204, and 206 through 208. Similarly, block 212 includes pages 214, and 216 through 218 and block 222 includes pages 224, and 226 through 228. SSD 200 supports page reads, page writes, and block erases. The logical components 100 may be stored on SSD 200.
One operation performed by dedupe systems is finding sub-blocks in one data item (e.g., file) that are related to sub-blocks in another data item (e.g., file) so that the duplicate items can be removed, not stored, and/or not transmitted. Finding related (e.g., duplicate, similar) sub-blocks may involve accessing both an index and a repository. As described above, RAM, disk, and SSD may have different strengths and weaknesses and may have different performance characteristics for different operations.
The foregoing statements are not intended to constitute an admission that any patent, publication or other information referred to herein is prior art with respect to this disclosure. Rather, these statements serve to present a general discussion of technology and associated issues in the technology.